package xiaomin.demo.algorithm;

import java.util.HashMap;
import java.util.Map;
/*
给定 N 个 整数， N 为 偶数， 是否 能 找到 N/ 2 对，
使得 每 对 和 能被 k 整除。 注意： 每个 元素 只能 出现 在 一个 配对 中。

陈东锋. 进军硅谷:程序员面试揭秘 (技术移民参考手册) (p. 72). 电子工业出版社. Kindle 版本.

思路：
1.遍历数组,构造哈希表,Key:余数（每个整数对K取余:结果取值范围为0~K-1） value：该余数的个数
2.0的数量不为偶数,则返回false
3.k如果是偶数,k/2的数量如果不为偶数,则返回false
4.遍历数组,x,的个数必须和k-x的个数相等,否则返回false
 */
public class Lesson09 {

    public static void run(){
        int[] a ={1,2,2,4,2,7};
        int k=4;
        boolean pair=true;

        Map<Integer,Integer> dic=new HashMap<Integer,Integer>();

        for(int x:a){
            int yu=x%k;
            if(!dic.containsKey(yu)){
                dic.put(yu,0);
            }
            dic.put(yu,dic.get(yu)+1);
        }

        if(dic.containsKey(0) && dic.get(0)%2!=0){//{4,4,4,1,2,7};
            pair =false;
            System.out.println(pair);
            return;
        }
        if(k%2==0 && dic.containsKey(k/2) && dic.get(k/2)%2!=0){//{2,2,2,1,3,7};
            pair=false;
            System.out.println(pair);
            return;
        }

        int i=1;
        while (i<k/2){
            if(!dic.get(i).equals(dic.get(k-i))){
                pair=false;
            }
            i++;
        }

        System.out.println(pair);
    }
}
